package MAIN;

import java.util.*;

//笔试强训第20天
//选择题
/*设度为2的节点数为n2，度为1的节点数为n1，度为0的节点数为n0，此时n0 + n1 + n2 = 总节点个数，n2 + 1 = n0
* 前序遍历和中序遍历相同，此时这棵树一定是单分支的树，层序遍历的结果仍然是和前中序遍历的顺序是一样的*/
/*数组元素进行堆化的过程，从最后一个非叶子节点开始进行元素的下沉操作（向下调整），元素调整的顺序是按照数组从后
* 往前排列的 */
/*在趋近于有序的数组中，冒泡排序是比较优秀的，当发现元素没有交换时，认为此时的数组就是有序的了，归并排序和堆排序
* 都是稳定的排序，时间复杂度都是N*logn。*/
public class Main20 {
    //公共子串计算
    public static int getMaxLen(String str1, String str2) {
        char[] arr1 = str1.toCharArray();
        char[] arr2 = str2.toCharArray();
        int len1 = str1.length();
        int len2 = str2.length();
        int[][] maxSubLen = new int[len1+1][len2+1];
        int maxLen = 0;//表示最大公共子串长度
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (arr1[i-1] == arr2[j-1]) {
                    //F(i,j) = F(i-1,j-1) + 1
                    maxSubLen[i][j] = maxSubLen[i-1][j-1] + 1;
                    //看是否需要更新最大值
                    if (maxLen < maxSubLen[i][j]) {
                        maxLen = maxSubLen[i][j];
                    }
                }
            }
        }
        return maxLen;
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        while (scan.hasNextLine()) {
            String s1 = scan.nextLine();
            String s2 = scan.nextLine();
            System.out.println(getMaxLen(s1,s2));
        }
    }
    //反转字符串
    public static void main2(String[] args) {
        Scanner scan = new Scanner(System.in);
        while (scan.hasNextLine()) {
            String s = scan.nextLine();
            char[] chs = s.toCharArray();
            int left = 0;
            int right = chs.length - 1;
            while (left < right) {
                char tmp = chs[left];
                chs[left] = chs[right];
                chs[right] = tmp;
                left++;
                right--;
            }
            for (int i = 0; i < chs.length; i++) {
                System.out.println(chs[i]);
            }
        }

    }
    public static void main1(String[] args) {
        //字符串反转后的字符串
        Scanner scan = new Scanner(System.in);
        while (scan.hasNextLine()) {
            String str = scan.nextLine();
            //进行反转
            for (int i = str.length()-1; i >= 0; i--) {
                char ch = str.charAt(i);
                System.out.print(ch);
            }
        }
    }


}
